Data redundancy enables the availability of data in the circumstance that one or more storage nodes fail. Many enterprise storage systems (e.g., Network Attached Storage (NAS), Storage Area Network (SAN)) and cloud storage systems (e.g. Object Storage, Key Value Store) employ data redundancy mechanisms in order to provide fault tolerance. Data redundancy may be classified into two categories: replica based and erasure coding based. A classical three-replica approach keeps three copies for one data content and stores them into three storage nodes, which triples the cost. When this method is applied to a distributed storage system with, for example, 100 nodes, if more than two servers fail, there may be a high probability that some of the data will become unavailable.
Conventional erasure coding implementations in enterprise storage may include RAID (redundant array of independent disks), Reed-Solomon, and Cauchy Reed-Solomon erasure coding. Erasure coding uses the notation “N+M” to denote N data blocks and M redundancy blocks generated by the encoding of N data blocks. That is, N data blocks may be encoded to generate N+M total blocks. The extra cost of encoding may be defined as M/N. For example, an “8+2” coding implemented in a 100 node system may still have a certain probability for data unavailability.
It may be desirable to be able to run erasure coding at a much larger scale, such as an “80+20” coding using 100 servers. In this case, with 25% extra disk usage, the system may guarantee 100% data availability even if 20 of the 100 servers fail. A significant challenge in implementing such a system may be that the computing complexity increases linearly with the scale. Thus, there is a demand for the development of optimized software erasure coding/decoding calculation and parallel data recovery in order to outperform and improve upon the efficiency of conventional systems that are not sufficient for large-scale implementations.